package 算法.leetcode.offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author lchenglong
 * @date 2022/3/19
 */
public class Offer57_2 {

    public static void main(String[] args) {
        Offer57_2 instance = new Offer57_2();
        int[][] ans = instance.findContinuousSequence2(15);
        for (int[] subAns :ans){
            System.out.println(Arrays.toString(subAns));
        }
    }
    public int[][] findContinuousSequence(int target) {
        if (target<3) return new int[][]{{target}};
        int start=-1,end = -1,sum=0;
        List<int[]> ans = new ArrayList<int[]>();
        List<String> list = new ArrayList<String>();
        for (int i=0;i<=(target+1)/2;i++) {
            if (start == -1)start = i;
            if (end == -1) end = i;
            sum +=i;
            end++;
            if (sum == target) {
                list.add(start+"_"+end);
                end = i = ++start;
                sum = 0;
            }
            if (sum > target){
                end =i= ++start;
                sum = 0;
            }
        }
        for (int idx = 0;idx<list.size();idx++){
            String[] arr = list.get(idx).split("_");
            int i = Integer.parseInt(arr[0]);
            int j= Integer.parseInt(arr[1]);
            j = i==0?j-1:j;
            int[] subAns = new int[j-i];
            int count = 0;
            for (int k = i+1;k<=j;k++) {
                subAns[count++] = k;
            }
            ans.add(subAns);
        }
        return ans.toArray(new int[ans.size()][]);
    }

    public int[][] findContinuousSequence2(int target) {
        List<int[]> ans = new ArrayList<int[]>();
        for (int l=1,r=2;l<r;){
            int sum = (l+r)*(r-l+1)/2;
            if (sum == target) {
                int[] subArray = new  int[r-l+1];
                for (int i= l;i<=r;i++) {
                    subArray[i-l] =  i;
                }
                ans.add(subArray);
                l++;
            } else if (sum<target) {
                r++;
            } else {
                l++;
            }
        }
        return ans.toArray(new int[ans.size()][]);
    }
}
